import time
#装置器
def cal_time(func):
    def wrapper(*args,**kwargs):
        t1=time.time()
        result=func(*args,**kwargs)
        t2=time.time()
        print("%s running time: %s secs."%(func.__name__,t2-t1))
        return result
    return wrapper

p=[0,1,5,8,9,10,17,17,20,21,23,2,26,27,27,28,30,33,36,39,40]
#p=[0,1,5,8,9,10,17,17,20,24,30]

def cut_rod_recursion(p,n):
    if n==0:
        return 0
    else:
        res=p[n]
        for i in range(1,n):
            res=max(res,cut_rod_recursion(p,i)+cut_rod_recursion(p,n-i))
        return res
@cal_time
def c1(p,n):
    return cut_rod_recursion(p,n)

def cut_rod_rescursion2(p,n):
    if n==0:
        return 0
    else:
        res=0
        for i in range(1,n+1):
            res=max(res,p[i]+cut_rod_rescursion2(p,n-i))
        return res
@cal_time
def c2(p,n):
    return cut_rod_rescursion2(p,n)
print(c1(p,10))
print(c2(p,10))